package ljl.alg.jianzhioffer.round3.hard;

public class _51_reversePairs {

    class lufei {
        int[] nums, tmp;
        public int reversePairs(int[] nums) {
            this.nums = nums;
            tmp = new int[nums.length];
            return mergeSort(0, nums.length - 1);
        }
        private int mergeSort(int l, int r) {
            // 终止条件
            if (l >= r) return 0;
            // 递归划分
            int m = (l + r) / 2;
            int res = mergeSort(l, m) + mergeSort(m + 1, r);
            // 合并阶段
            int i = l, j = m + 1;
            for (int k = l; k <= r; k++)
                tmp[k] = nums[k];
            for (int k = l; k <= r; k++) {
                if (i == m + 1)
                    nums[k] = tmp[j++];
                else if (j == r + 1 || tmp[i] <= tmp[j])
                    nums[k] = tmp[i++];
                else {
                    nums[k] = tmp[j++];
                    res += m - i + 1; // 统计逆序对
                }
            }
            return res;
        }
    }

    class test {
        public int reversePairs(int[] nums) {
            return merge(nums, new int[nums.length], 0, nums.length - 1);
        }
        private int merge(int[] nums, int[] tmp, int l, int r) {
            if (l >= r) return 0;
            int m = (l + r) / 2;
            int res = merge(nums, tmp, l, m) + merge(nums, tmp, m + 1, r);
            System.arraycopy(nums, l, tmp, l, r + 1 - l);
            for (int i = l, k = l, j = m + 1; k <= r; k++) {
                if (i == m + 1) nums[k] = tmp[j++];
                else if (j == r + 1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++];
                else {
                    nums[k] = tmp[j++];
                    res += m - i + 1;
                }
            }
            return res;
        }
    }

}
